package _0496_Next_Greater_Element_I;

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;
import java.util.HashMap;

/**
 * Date: 2021/9/20 19:56
 * Content:
 * 执行用时：3 ms, 在所有 Java 提交中击败了93.36%的用户
 * 内存消耗：38.1 MB, 在所有 Java 提交中击败了98.85%的用户
 */
public class Solution {

    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        Deque<Integer> stk = new ArrayDeque<>();
        int[] q = new int[nums2.length];
        for (int i = nums2.length - 1; i >= 0; i--) {
            int x = nums2[i];
            while (!stk.isEmpty() && x >= stk.peek()) stk.pop();
            if (stk.isEmpty()) q[i] = -1;
            else q[i] = stk.peek();
            stk.push(x);
        }

        HashMap<Integer, Integer> hash = new HashMap<>();
        for (int i = 0; i < nums2.length; i++) hash.put(nums2[i], i);

        int[] res = new int[nums1.length];
        for (int i = 0; i < nums1.length; i++) res[i] = q[hash.get(nums1[i])];
        return res;
    }

    public static void main(String[] args) {

        int[] nums1 = {4, 1, 2}, nums2 = {1, 3, 4, 2};
        System.out.println(Arrays.toString((new Solution()).nextGreaterElement(nums1, nums2)));
    }
}
